package likou;

import java.util.*;
import java.util.concurrent.DelayQueue;

/**
 * @description: 移除元素
 * @title: RemoveElementDemo
 * @author: zp
 * @date: 2021/11/27 15:16
 */
public class RemoveElementDemo {
    public static void main(String[] args) {
        /*char[][] board =
                       {{'.', '.', '.', '.', '5', '.', '.', '1', '.'},
                        {'.', '4', '.', '3', '.', '.', '.', '.', '.'},
                        {'.', '.', '.', '.', '.', '3', '.', '.', '1'},
                        {'8', '.', '.', '.', '.', '.', '.', '2', '.'},
                        {'.', '.', '2', '.', '7', '.', '.', '.', '.'},
                        {'.', '1', '5', '.', '.', '.', '.', '.', '.'},

                        {'.', '.', '.', '.', '.', '2', '.', '.', '.'},
                        {'.', '2', '.', '9', '.', '.', '.', '.', '.'},
                        {'.', '.', '4', '.', '.', '.', '.', '.', '.'}};
        System.out.println(isValidSudoku(board));*/
        //reverseString("hello".toCharArray());
        //System.out.println(firstUniqChar("dddccdbba"));
        //System.out.println(isPalindrome("abccccdd"));
//        ListNode head = new ListNode(1);
//        ListNode node1 = new ListNode(2);
//        ListNode node2 = new ListNode(3);
//        ListNode node3 = new ListNode(4);
//        ListNode node4 = new ListNode(5);
//        head.next = node1;
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        reverseList(head);
//        TreeNode treeNode1 = new TreeNode(1);
//        TreeNode treeNode2 = new TreeNode(2);
//        TreeNode treeNode3 = new TreeNode(2);
//        TreeNode treeNode4 = new TreeNode(3);
//        TreeNode treeNode5 = new TreeNode(3);
//        TreeNode treeNode6 = new TreeNode(4);
//        TreeNode treeNode7 = new TreeNode(4);
//        treeNode1.left = treeNode2;
//        treeNode2.left = treeNode4;
//        treeNode2.right = treeNode6;
//        treeNode1.right = treeNode3;
//        treeNode3.left = treeNode5;
//        treeNode3.right = treeNode7;
//        System.out.println(isSymmetric(treeNode1));
//        System.out.println(climbStairs(1));
        //System.out.println(pivotIndex(new int[]{1,7,3,6,5,6}));
//        int[][] ints = new int[][]{
//                {1,1,1},
//                {1,0,1},
//                {1,1,1}
//        };
//        setZeroes(ints);
//        for (int i = 0; i <ints.length ; i++) {
//            System.out.println(Arrays.toString(ints[i]));
//        }
        //System.out.println(reverseWords("  Bob    Loves  Alice   "));
        //arrayPairSum(new int[]{1,4,3,2});
        //System.out.println(Arrays.toString(twoSum(new int[]{-1,0},-1)));
        //System.out.println(mySqrt(8));
        //System.out.println(generate(5));
        //System.out.println(Arrays.toString(decrypt(new int[]{2,4,9,3},-2)));
        //System.out.println(9%4);
        //System.out.println(getMaximumGenerated(0));
        //System.out.println(Arrays.toString(smallestK(new int[]{1, 3, 5, 7, 2, 4, 6, 8}, 4)));
        //System.out.println(findMaximumXOR(new int[]{8,10,2}));
        //System.out.println(countAndSay(3));
        //System.out.println(missingNumber(new int[]{3,0,1}));
        //源文件地址
//        String srcFilePath = "C:\\Users\\MSI-NB\\Desktop\\dd.txt";
//        //压缩后的文件名
//        String desFileName = "ddCode.txt";
//        //压缩文件的位置
//        String desFileLoc = "C:\\Users\\MSI-NB\\Desktop\\";
//        //解压后的文件名
//        String unCompressedFilePath = "C:\\Users\\MSI-NB\\Desktop\\unddCode.txt";
//
//        LZW tool = new LZW(srcFilePath, desFileLoc, desFileName);
//        //压缩文件
//        tool.compress();
//
//        //解压文件
//        tool.unCompress(desFileLoc + desFileName, unCompressedFilePath);
        //firstMissingPositive(new int[]{1,7,8,9,-2,-1,0,2,3,4,5});

        //topKFrequent(new String[]{"i","love","leetcode","i","love","coding"},2);
        //largestPerimeter(new int[]{1,1,2,2});
        //intersect1(new int[]{1,2,2,1},new int[]{2,2});
        //System.out.println(Arrays.toString(findWords(new String[]{"Hello","Alaska","Dad","Peace"})));
        //System.out.println(isHappy(2));
        //nextGreaterElement(new int[]{4,1,2},new int[]{1,3,4,2});
        //sumOddLengthSubarrays(new int[]{1,4,2,5,3});
        //moveZeroes1(new int[]{0,1,0,3,12});
        //diagonalSum(new int[][]{{7, 3, 1, 9}, {3, 4, 6, 9}, {6, 9, 6, 6}, {9, 5, 8, 5}});
        //mergeAlternately("abc", "qwe");
        //freqAlphabets("10#11#12");
        //sortByBits(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8});
//        int[][] ints = new int[][]{
//                {1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}
//        };
//        findNumberIn2DArray(ints, 5);
        //multiply("123456789","987654321");
        //System.out.println(1^2);
        //addToArrayForm(new int[]{3,4,1},66);
        //kClosest(new int[][]{{2,2},{2,2},{2,2},{2,2},{2,2},{2,2},{1,1}},1);
        //checkArithmeticSubarrays(new int[]{4,6,5,9,3,7},new int[]{0,0,2},new int[]{2,3,5});
        //longestPalindrome("adam");
//        ListNode listNode1 = new ListNode(1);
//        ListNode listNode2 = new ListNode(2);
//        ListNode listNode3 = new ListNode(3);
//        ListNode listNode4 = new ListNode(4);
//        ListNode listNode5 = new ListNode(5);
//        listNode1.next = listNode2;
//        listNode2.next = listNode3;
//        listNode3.next = listNode4;
//        listNode4.next = listNode5;
//        reorderList(listNode1);
        // wordBreak("ab", Arrays.asList("a", "b"));
        //mostCommonWord("Bob. hIt, baLl",new String[]{"hit","bob"});
        //summaryRanges(new int[]{0,2,3,4,6,8,9});
        //findDisappearedNumbers(new int[]{4,3,2,7,8,2,3,1});
        //uniqueOccurrences(new int[]{1,2,2,1,1,3});
        //minimumAbsDifference(new int[]{3,8,-10,23,19,-4,-14,27});
        //smallestRangeI(new int[]{1,3,6},3);
        //sortArrayByParity(new int[]{3, 1, 2, 4});
        //minDeletionSize(new String[]{"a","b"});
        //findLucky(new int[]{2,2,2,3,3});
        //minSubArrayLen(15,new int[] {1,2,3,4,5});
        //stringMatching(new String[]{"leetcoder","leetcode","od","hamlet","am"});
        reverseLeftWords("abcdefg", 2);
    }

    /**
     * @description: 移除给定的元素 并把移除之后的数组大小返回
     * @author: zp
     * @date: 2021/11/28 20:49
     * @param: nums
     * @param: val
     * @return: int
     */
    public static int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[count] = nums[i];
                count++;
            }
        }

        return count;
    }

    /**
     * @description: 发现子字符串是否存在大字符串里面 如果存在返回第一次出现的下标 如果不存在返回-1
     * @author: zp
     * @date: 2021/11/27 16:18
     * @param: ss
     * @param: pp
     * @return: int
     */
    public static int strStr(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        // 枚举原串的「发起点」
        for (int i = 0; i <= n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
            int a = i, b = 0;
            while (b < m && s[a] == p[b]) {
                a++;
                b++;
            }
            // 如果能够完全匹配，返回原串的「发起点」下标
            if (b == m) {
                return i;
            }
        }
        return -1;
    }

    /**
     * @description: 图像翻转给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
     * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
     * @author: zp
     * @date: 2021/11/28 20:48
     * @param: matrix
     * @return: void
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }

    /**
     * @description: 查找到元素 如果元素在数组中返回元素下标 如果不存在返回该插入的位置下标（数组元素为升序排列）
     * 给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，
     * 并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 请必须使用时间复杂度为 O(log n) 的算法。
     * @author: zp
     * @date: 2021/11/28 20:49
     * @param: nums
     * @param: target
     * @return: int
     */
    public static int searchInsert(int[] nums, int target) {
        return search(nums, target, 0, nums.length - 1);
    }

    /**
     * @description: 二分查找法
     * @author: zp
     * @date: 2021/11/28 20:52
     * @param: nums
     * @param: target
     * @param: left
     * @param: right
     * @return: int
     */
    public static int search(int[] nums, int target, int left, int right) {
        if (left > right) {
            return right;
        }
        if (nums[left] > target) {
            return left;
        } else if (nums[right] < target) {
            return right + 1;
        }
        int mid = (right + left) / 2;
        int value = nums[mid];
        if (target > value) {
            return search(nums, target, mid + 1, right);
        } else if (target < value) {
            return search(nums, target, left, mid - 1);
        } else {
            return mid;
        }
    }

    /**
     * @description: 给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。
     * A -> 1
     * B -> 2
     * C -> 3
     * ...
     * Z -> 26
     * AA -> 27
     * AB -> 28
     * @author: zp
     * @date: 2021/12/1 19:53
     * @param: columnNumber
     * @return: java.lang.String
     */
    public static String convertToTitle(int columnNumber) {
        StringBuilder sb = new StringBuilder();
        while (columnNumber > 0) {
            int a0 = (columnNumber - 1) % 26 + 1;
            sb.append((char) (a0 - 1 + 'A'));
            columnNumber = (columnNumber - a0) / 26;
        }
        return sb.reverse().toString();
    }

    /**
     * @description: 移动0 把数组的0都移动到最后
     * @author: zp
     * @date: 2022/1/2 16:25
     * @param: nums
     * @return: void
     */
    public void moveZeroes(int[] nums) {
        int i, j = 0;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        while (j < nums.length) {
            nums[j++] = 0;
        }
    }

    /**
     * @description: 编写一个函数，输入是一个无符号整数（以二进制串的形式）
     * ，返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）
     * @author: zp
     * @date: 2022/1/2 16:33
     * @param: n
     * @return: int
     */
    public int hammingWeight1(int n) {
        int ret = 0;
        while (n != 0) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }

    /**
     * @description: 买卖股票的最佳时机 II
     * @author: zp
     * @date: 2022/1/2 19:55
     * @param: prices
     * @return: int
     * 给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
     * <p>
     * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
     * <p>
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     */
    public int maxProfit(int[] prices) {
        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            sum += Math.max(prices[i] - prices[i - 1], 0);
        }
        return sum;
    }

    /**
     * @description: 旋转数组
     * @author: zp
     * @date: 2022/1/2 20:04
     * @param: nums
     * @param: k
     * @return: void
     */
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }
    /*public void rotate(int[] nums, int k) {
        int temp;
        for (int i = 0; i <k ; i++) {
            for (int j = nums.length-2; j >0 ; j--) {
                temp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = temp;
            }
        }
    } 超出时间限制*/

    /**
     * @description: 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，
     * 应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。（遍历的方式 时间复杂度较高）
     * @author: zp
     * @date: 2022/1/9 16:56
     * @param: nums1
     * @param: nums2
     * @return: int[]
     */
    public static int[] intersect1(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> list = new ArrayList<>();
        int count = 0;
        if (nums1.length < nums2.length) {
            for (int value : nums1) {
                while (count < nums2.length) {
                    if (value == nums2[count]) {
                        list.add(value);
                        count++;
                        break;
                    } else if (value < nums2[count]) {
                        break;
                    }
                    count++;
                }
            }
        } else {
            for (int value : nums2) {
                while (count < nums1.length) {
                    if (value == nums1[count]) {
                        list.add(value);
                        count++;
                        break;
                    } else if (value < nums1[count]) {
                        break;
                    }
                    count++;
                }
            }
        }
        int[] sum = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            sum[i] = list.get(i);
        }
        return sum;
    }

    /**
     * @description: 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
     * <p>
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
     * @author: zp
     * @date: 2022/1/10 20:01
     * @param: board
     * @return: boolean
     */
    public static boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] subboxes = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * @description: 反转字符串
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * <p>
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     * @author: zp
     * @date: 2022/1/11 20:05
     * @param: s
     * @return: void
     */
    public static void reverseString(char[] s) {
        System.out.println(Arrays.toString(s));
        char temp;
        int length = s.length;
        for (int i = 0; i < length / 2; i++) {
            temp = s[i];
            s[i] = s[length - i - 1];
            s[length - i - 1] = temp;
        }
        System.out.println(Arrays.toString(s));
    }

    /**
     * @description: 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
     * @author: zp
     * @date: 2022/1/11 20:13
     * @param: s
     * @return: int
     */
    public static int firstUniqChar(String s) {
        char[] cs = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < cs.length; i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        for (int i = 0; i < s.length(); ++i) {
            if (map.get(s.charAt(i)) == 1) {
                return i;
            }
        }

        return -1;
    }

    /**
     * @description: 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     * <p>
     * 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
     * @author: zp
     * @date: 2022/1/11 20:52
     * @param: s
     * @param: t
     * @return: boolean
     */
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();

        Arrays.sort(cs);
        Arrays.sort(ct);

        for (int i = 0; i < cs.length; i++) {
            if (cs[i] != ct[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * @description: 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
     * <p>
     * 说明：本题中，我们将空字符串定义为有效的回文串。
     * @author: zp
     * @date: 2022/1/11 20:56
     * @param: s
     * @return: boolean
     */
    public static boolean isPalindrome(String s) {
        s = s.toUpperCase();
        char[] cs = s.toCharArray();
        int length = s.length();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < length; i++) {
            if ((cs[i] >= 48 && cs[i] <= 57) || (cs[i] >= 65 && cs[i] <= 90)) {
                stringBuilder.append(cs[i]);
            }

        }

        char[] ccs = stringBuilder.toString().toCharArray();
        int csLength = ccs.length;
        for (int i = 0; i < csLength / 2; i++) {
            if (ccs[i] != ccs[csLength - 1 - i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * @description: 请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
     * <p>
     * 题目数据保证需要删除的节点 不是末尾节点 。
     * @author: zp
     * @date: 2022/1/12 19:55
     * @param: node
     * @return: void
     */
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    /**
     * @description: 反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * @author: zp
     * @date: 2022/1/12 19:56
     * @param: head
     * @return: likou.ListNode
     */
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    /**
     * @description: 回文链表
     * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     * @author: zp
     * @date: 2022/1/14 19:41
     * @param: head
     * @return: boolean
     */
    public boolean isPalindrome(ListNode head) {
        List<ListNode> listNodes = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            listNodes.add(temp);
            temp = temp.next;
        }
        int length = listNodes.size();
        for (int i = 0; i < length / 2; i++) {
            if (listNodes.get(i).val != listNodes.get(length - 1 - i).val) {
                return false;
            }
        }
        return true;
    }

    /**
     * @description: 环形链表
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     * <p>
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * <p>
     * 如果链表中存在环，则返回 true 。 否则，返回 false 。
     * @author: zp
     * @date: 2022/1/14 19:48
     * @param: head
     * @return: boolean
     */
    public boolean hasCycle(ListNode head) {
        Map<ListNode, Integer> map = new HashMap<>();
        ListNode temp = head;
        while (temp != null) {
            if (!map.containsKey(temp)) {
                map.put(temp, 0);
            } else {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    /**
     * @description: 对称二叉树
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     * @author: zp
     * @date: 2022/1/14 19:56
     * @param: root
     * @return: boolean
     */
    public static boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public static boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }

    /**
     * @description: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * <p>
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * <p>
     * 注意：给定 n 是一个正整数。
     * @author: zp
     * @date: 2022/1/18 20:45
     * @param: n
     * @return: int
     */
    public static int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    /**
     * @description: 寻找数组的中心索引
     * 给你一个整数数组 nums ，请计算数组的 中心下标 。
     * <p>
     * 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
     * <p>
     * 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
     * <p>
     * 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
     * @author: zp
     * @date: 2022/1/23 15:55
     * @param: nums
     * @return: int
     */
    public static int pivotIndex(int[] nums) {
        int length = nums.length;
        int sum = 0;
        int num = 0;
        //先计算数列之和
        for (int i = 0; i < length; i++) {
            sum += nums[i];
        }
        //如果中心下标位于数组最左端，那么左侧数之和视为 0
        if (sum - nums[0] == 0) {
            return 0;
        }
        //否则从第二个元素开始遍历 除去自己之外 减去sum左边的元素 num加上左边的元素

        for (int i = 1; i < length; i++) {
            num += nums[i - 1];
            sum -= nums[i - 1];
            //比较是否相等（需要排除检测的这个元素使用num从nums[i-1]开始 sum比较的时候减去nums[i]）
            if (sum - nums[i] == num) {
                return i;
            }
        }
        return -1;
    }

    /**
     * @description: 零矩阵
     * 编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
     * @author: zp
     * @date: 2022/1/25 19:50
     * @param: matrix
     * @return: void
     */
    public static void setZeroes(int[][] matrix) {
        List<Integer> row = new ArrayList<>();
        List<Integer> col = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    //计算0出现的行 如果已经保存就跳过 因为同一行出现0 都要被设置为0
                    if (!row.contains(i)) {
                        row.add(i);
                    }
                    //计算0出现的列 如果已经保存就跳过 因为同一列出现0 都要被设置为0
                    if (!col.contains(j)) {
                        col.add(j);
                    }
                }
            }
        }
        //判断行里面有没有出现0 如果出现遍历行都设置为0
        if (row.size() != 0) {
            for (int x : row) {
                Arrays.fill(matrix[x], 0);
            }
        }
        //判断列里面有没有存在0 如果有设置为0
        if (col.size() != 0) {
            for (int y : col) {
                for (int i = 0; i < matrix.length; i++) {
                    matrix[i][y] = 0;
                }
            }
        }
    }

    /**
     * @description: 翻转字符串里的单词
     * 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
     * <p>
     * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
     * <p>
     * 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
     * <p>
     * 说明：
     * <p>
     * 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
     * 翻转后单词间应当仅用一个空格分隔。
     * 翻转后的字符串中不应包含额外的空格。
     * @author: zp
     * @date: 2022/1/25 20:14
     * @param: s
     * @return: java.lang.String
     */
    public static String reverseWords(String s) {
        s = s.trim();
        int start = 0;
        int length = s.length();
        String s1 = "";
        for (int i = 0; i < length; i++) {
            if (s.charAt(i) != ' ') {
                start = i;
                while (i < length && s.charAt(i) != ' ') {
                    i++;
                }
                s1 = s.substring(start, i) + " " + s1;
            }
        }
        return s1.trim();
    }

    /**
     * @description: 数组拆分 I
     * 给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对,
     * 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
     * <p>
     * 返回该 最大总和 。
     * @author: zp
     * @date: 2022/2/7 20:04
     * @param: nums
     * @return: int
     */
    public static int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += Math.min(nums[i], nums[i + 1]);
        }
        return sum;
    }

    /**
     * @description: 两数之和 II - 输入有序数组
     * 给定一个已按照 非递减顺序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
     * <p>
     * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。
     * numbers 的下标 从 1 开始计数 ，
     * 所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
     * <p>
     * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
     * @author: zp
     * @date: 2022/2/7 20:16
     * @param: numbers
     * @param: target
     * @return: int[]
     * 使用二分查找的方式降低时间复杂度 从N^2复杂度变为NlogN的时间复杂度
     */
    public static int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }
    //暴力破解超出时间
//    public static int[] twoSum(int[] numbers, int target) {
//        for (int i = 0; i <numbers.length ; i++) {
//            for (int j = i+1; j <numbers.length ; j++) {
//                if(numbers[i]+numbers[j]>target){
//                    break;
//                }
//                if(numbers[i]+numbers[j]==target){
//                    return new int[]{i+1,j+1};
//                }
//            }
//        }
//        return new int[]{};
//    }

    /**
     * @description: x 的平方根
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * <p>
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * <p>
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     * @author: zp
     * @date: 2022/2/8 20:21
     * @param: x
     * @return: int
     */
    public static int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        //为了控制时间复杂度 使用二分法 先获取 mid = l + (r - l) / 2;
        // 如果小了往后加一 然后大了往前减一 如果比较数值是否一样
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    /**
     * @description: 合并两个有序数组
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     * <p>
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     * <p>
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，
     * nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n
     * @author: zp
     * @date: 2022/2/11 19:40
     * @param: nums1
     * @param: m
     * @param: nums2
     * @param: n
     * @return: void
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //拼接两个数组 然后排序
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
        Arrays.sort(nums1);
    }

    /**
     * @description: 杨辉三角
     * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
     * <p>
     * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
     * @author: zp
     * @date: 2022/2/11 19:45
     * @param: numRows
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     */
    public static List<List<Integer>> generate(int numRows) {
        List<Integer> list;
        List<Integer> lastList;
        List<List<Integer>> lists = new ArrayList<>();
        lists.add(Collections.singletonList(1));
        if (numRows == 1) {
            return lists;
        }
        lists.add(Arrays.asList(1, 1));
        if (numRows == 2) {
            return lists;
        }
        int count;
        for (int i = 2; i < numRows; i++) {
            //获取到前一个数组 因为杨辉三角的值等于 前后是1 等n值等于 上一个数组的第 n = numRows[n]+numRows[n-1];
            lastList = lists.get(i - 1);
            list = new ArrayList<>();
            //第一个和最后一个都是1
            list.add(1);
            for (int j = 1; j < i; j++) {
                count = lastList.get(j) + lastList.get(j - 1);
                list.add(count);
            }
            list.add(1);
            lists.add(list);
        }
        return lists;
    }

    /**
     * @description: 二叉树的前序遍历
     * @author: zp
     * @date: 2022/2/11 19:59
     * @param: root
     * @return: java.util.List<java.lang.Integer>
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preorderTraversal(root, list);
        return list;
    }

    public void preorderTraversal(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        if (root.left != null) {
            preorderTraversal(root.left, list);
        }
        if (root.right != null) {
            preorderTraversal(root.right, list);
        }
    }

    /**
     * @description: 二叉树的中序序遍历
     * @author: zp
     * @date: 2022/2/11 19:59
     * @param: root
     * @return: java.util.List<java.lang.Integer>
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorderTraversal(root, list);
        return list;
    }

    public void inorderTraversal(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            inorderTraversal(root.left, list);
        }
        list.add(root.val);
        if (root.right != null) {
            inorderTraversal(root.right, list);
        }
    }

    /**
     * @description: 二叉树的后序遍历
     * @author: zp
     * @date: 2022/2/11 20:10
     * @param: root
     * @return: java.util.List<java.lang.Integer>
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postorderTraversal(root, list);
        return list;
    }

    public void postorderTraversal(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            postorderTraversal(root.left, list);
        }
        if (root.right != null) {
            postorderTraversal(root.right, list);
        }
        list.add(root.val);
    }

    /**
     * @description: 最大重复子字符串
     * 给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 
     * sequence 的一个子字符串，那么单词 word 的 重复值为 k 。
     * 单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。
     * 如果 word 不是 sequence 的子串，那么重复值 k 为 0 。
     * 给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。
     * 其实这道题也可以使用KMP算法 只是找到之后继续寻找 直到找到字符串结尾 如果找到把比较值恢复 并把count++ 字符串下标移动word的长度
     * @author: zp
     * @date: 2022/2/13 19:10
     * @param: sequence
     * @param: word
     * @return: int
     */
    public static int maxRepeating(String sequence, String word) {
        int count = 0;
        //获取到需要找到的字符串 转成stringBuilder
        StringBuilder sb = new StringBuilder(word);
        //循环调用contains方法 看看是否存在 如果存在就count++ 然后继续拼接word 然后在判断
        while (sequence.contains(sb)) {
            count++;
            sb.append(word);
        }
        return count;
    }

    /**
     * @description: 拆炸弹
     * 你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。
     * <p>
     * 为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。
     * <p>
     * 如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
     * 如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
     * 如果 k == 0 ，将第 i 个数字用 0 替换。
     * 由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。
     * <p>
     * 给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！
     * @author: zp
     * @date: 2022/2/16 19:39
     * @param: code
     * @param: k
     * @return: int[]
     */
    public static int[] decrypt(int[] code, int k) {
        int[] nums = new int[code.length];
        //当k等于0 直接返回数组
        if (k == 0) {
            return nums;
        }
        int length = nums.length;
        int count = 0;
        int num = Math.abs(k);
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < num; j++) {
                //通过求余的方式 获取位置上的数据 相加 等到数值
                if (k > 0) {
                    count += code[(length + j + 1 + i) % length];
                } else {
                    count += code[(length + j + i - num) % length];
                }

            }
            //把相加单数赋值到数组当中 并把count置为0
            nums[i] = count;
            count = 0;
        }
        return nums;
    }

    /**
     * @description: 获取生成数组中的最大值
     * 给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
     * <p>
     * nums[0] = 0
     * nums[1] = 1
     * 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
     * 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
     * 返回生成数组 nums 中的 最大 值。
     * @author: zp
     * @date: 2022/2/16 20:03
     * @param: n
     * @return: int
     */
    public static int getMaximumGenerated(int n) {
        if (n == 0) {
            return 0;
        }
        int[] nums = new int[n + 1];
        nums[1] = 1;
        for (int i = 0; i < nums.length; i++) {
            //当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
            if (i * 2 < nums.length) {
                nums[i * 2] = nums[i];
            }
            //当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
            if (i * 2 + 1 < nums.length) {
                nums[i * 2 + 1] = nums[i] + nums[i + 1];
            }
        }
        //计算出数组 然后排序 获取数组当中最后一个元素 就是数组中最大的值
        Arrays.sort(nums);
        return nums[n];
    }

    /**
     * @description: 检查两个字符串数组是否相等
     * 给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。
     * <p>
     * 数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。
     * @author: zp
     * @date: 2022/2/17 20:14
     * @param: word1
     * @param: word2
     * @return: boolean
     */
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        StringBuilder stringBuilder1 = new StringBuilder();
        StringBuilder stringBuilder2 = new StringBuilder();
        for (int i = 0; i < word1.length; i++) {
            stringBuilder1.append(word1[i]);
        }
        for (int i = 0; i < word2.length; i++) {
            stringBuilder2.append(word2[i]);
        }
        return (stringBuilder1.toString()).equals(stringBuilder2.toString());
    }

    /**
     * @description: 最小K个数
     * @author: zp
     * @date: 2022/2/19 16:36
     * @param: arr
     * @param: k
     * @return: int[]
     */
    public static int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        //构建大顶堆 默认是小顶堆 重写Comparator接口的方法
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int[] nums = new int[k];
        for (int i = 0; i < arr.length; i++) {
            //先把前k个元素放入优先队列当中
            if (i < k) {
                queue.offer(arr[i]);
            } else {
                //判断优先队列是否为空
                if (queue.isEmpty()) {
                    return new int[0];
                }
                //取出第一个元素 因为是大顶堆 所以是整个队列当中最大的元素 如果数组当中还要比堆顶元素更小的元素
                //把堆顶元素弹出 然后把arr[i]元素加入优先队列当中
                int top = queue.peek();
                if (arr[i] < top) {
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }

        }
        int count = queue.size();
        for (int i = 0; i < count; i++) {
            nums[k - i - 1] = queue.poll();
        }

        return nums;
    }

    /**
     * @description: 使用排序的方式 获取第k个最小值
     * @author: zp
     * @date: 2022/2/19 17:02
     * @param: arr
     * @param: k
     * @return: int[]
     */
    public static int[] smallestK2(int[] arr, int k) {
        int[] nums = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < k; i++) {
            nums[i] = arr[i];
        }
        return nums;
    }

    /**
     * @description: 最大的异或
     * 给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
     * @author: zp
     * @date: 2022/2/19 17:09
     * @param: nums
     * @return: int
     */
    // 最高位的二进制位编号为 30
    static final int HIGH_BIT = 30;

    public int findMaximumXOR(int[] nums) {
        int x = 0;
        for (int k = HIGH_BIT; k >= 0; --k) {
            Set<Integer> seen = new HashSet<Integer>();
            // 将所有的 pre^k(a_j) 放入哈希表中
            for (int num : nums) {
                // 如果只想保留从最高位开始到第 k 个二进制位为止的部分
                // 只需将其右移 k 位
                seen.add(num >> k);
            }

            // 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
            // 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
            int xNext = x * 2 + 1;
            boolean found = false;

            // 枚举 i
            for (int num : nums) {
                if (seen.contains(xNext ^ (num >> k))) {
                    found = true;
                    break;
                }
            }

            if (found) {
                x = xNext;
            } else {
                // 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
                // 即为 x = x*2
                x = xNext - 1;
            }
        }
        return x;
    }

    //暴力算法 超出时间
    public static int findMaximumXOR2(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int count = nums[0] ^ nums[1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    continue;
                }
                count = Math.max(count, nums[i] ^ nums[j]);
            }
        }
        return count;
    }

    /**
     * @description: 山峰数组的顶部
     * 符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
     * <p>
     * arr.length >= 3
     * 存在 i（0 < i < arr.length - 1）使得：
     * arr[0] < arr[1] < ... arr[i-1] < arr[i]
     * arr[i] > arr[i+1] > ... > arr[arr.length - 1]
     * 给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
     * 很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？
     * @author: zp
     * @date: 2022/2/21 20:09
     * @param: arr
     * @return: int
     */
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        // 初始化从第二个和倒数第二个元素之间寻找山顶元素 因为第一个和最后一个元素不满足山顶元素的定义 直接不用比较
        int l = 1;
        int r = n - 2;
        int ans = 0;
        while (l <= r) {
            //找到中间元素 然后中间元素大于 中间元素的下一个元素 把ans的值替换 然后缩短右边的范围 r=mid-1
            //否则山顶元素就在mid的右边 l=mid+1 知道遍历完所有的元素
            int mid = (l + r) / 2;
            if (arr[mid] > arr[mid + 1]) {
                ans = arr[mid];
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return ans;
    }

    /**
     * @description: 外观数列（可以等价于游程编码）
     * 给定一个正整数 n ，输出外观数列的第 n 项。
     * <p>
     * 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
     * <p>
     * 你可以将其视作是由递归公式定义的数字字符串序列：
     * <p>
     * countAndSay(1) = "1"
     * countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
     * 前五项如下：
     * <p>
     * 1.     1
     * 2.     11
     * 3.     21
     * 4.     1211
     * 5.     111221
     * 第一项是数字 1
     * 描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
     * 描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
     * 描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
     * 描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
     * 要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
     * @author: zp
     * @date: 2022/2/21 20:33
     * @param: n
     * @return: java.lang.String
     */
    public static String countAndSay(int n) {
        String str;
        str = "1";
        if (n == 1) {
            return str;
        }
        for (int i = 1; i < n; i++) {
            str = str + "!";
            str = compress(str);
        }
        return str;
    }

    public static String compress(String str) {
        int count = 0;
        StringBuffer stringBuffer = new StringBuffer();
        char[] cs = str.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            for (int j = i; j < cs.length; j++) {
                if (cs[i] == cs[j]) {
                    count++;
                } else {
                    stringBuffer.append((char) (count + 48));
                    stringBuffer.append(cs[i]);
                    i += count - 1;
                    count = 0;
                    break;
                }
            }
        }
        return stringBuffer.toString();
    }

    /**
     * @description: 买卖股票的最佳时机
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * <p>
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * <p>
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     * @author: zp
     * @date: 2022/2/22 20:17
     * @param: prices
     * @return: int
     */
    public int maxProfit1(int[] prices) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }

    /**
     * @description: 打家劫舍
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * <p>
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     * @author: zp
     * @date: 2022/2/22 20:26
     * @param: nums
     * @return: int
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

    /**
     * @description: 逆波兰表达式求值
     * 根据 逆波兰表示法，求表达式的值。
     * <p>
     * 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
     * <p>
     * 注意 两个整数之间的除法只保留整数部分。
     * <p>
     * 可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
     * @author: zp
     * @date: 2022/2/23 19:45
     * @param: tokens
     * @return: int
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int num1;
        int num2;
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            switch (str) {
                case "+":
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 + num2);
                    break;
                case "-":
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 - num2);
                    break;
                case "*":
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 * num2);
                    break;
                case "/":
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 / num2);
                    break;
                default:
                    stack.push(Integer.parseInt(str));
                    break;
            }
        }
        return stack.pop();
    }

    /**
     * @description: 多数元素
     * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * <p>
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * @author: zp
     * @date: 2022/2/24 20:04
     * @param: nums
     * @return: int
     */
    public int majorityElement(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int num = nums.length / 2 + 1;
        int count = -1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int value : nums) {
            if (!map.containsKey(value)) {
                map.put(value, 1);
            } else {
                int sum = map.get(value) + 1;
                if (sum == num) {
                    count = value;
                }
                map.put(value, sum);

            }
        }
        return count;
    }

    /**
     * @description: 相交链表
     * <p>
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     * <p>
     * 自定义评测：
     * <p>
     * 评测系统 的输入如下（你设计的程序 不适用 此输入）：
     * <p>
     * intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
     * listA - 第一个链表
     * listB - 第二个链表
     * skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
     * skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
     * 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
     * @author: zp
     * @date: 2022/2/24 20:18
     * @param: headA
     * @param: headB
     * @return: likou.ListNode
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != null) {
            visited.add(tempA);
            tempA = tempA.next;
        }
        while (tempB != null) {
            if (visited.contains(tempB)) {
                return tempB;
            }
            tempB = tempB.next;
        }

        return null;
    }

    /**
     * @description: 同构字符串
     * 给定两个字符串 s 和 t ，判断它们是否是同构的。
     * <p>
     * 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
     * <p>
     * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
     * @author: zp
     * @date: 2022/2/27 15:27
     * @param: s
     * @param: t
     * @return: boolean
     */
    public boolean isIsomorphic(String s, String t) {
        for (int i = 0; i < s.length(); i++) {
            if (s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))) {
                return false;
            }
        }
        return true;
    }

    /**
     * @description: 存在重复元素 II
     * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
     * @author: zp
     * @date: 2022/2/27 15:43
     * @param: nums
     * @param: k
     * @return: boolean
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(num)) {
                int index = map.get(num);
                if (Math.abs(i - index) <= k) {
                    return true;
                } else {
                    map.put(num, i);
                }
            } else {
                map.put(num, i);
            }


        }
        return false;
    }

    /**
     * @description: 丢失的数字
     * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
     * @author: zp
     * @date: 2022/2/27 15:52
     * @param: nums
     * @return: int
     */
    public static int missingNumber(int[] nums) {
        //解法一 排序
        // Arrays.sort(nums);
        // for(int i = 0; i < nums.length; i++){
        //     if(nums[i] != i) return i;
        // }
        // return nums.length;

        //解法二 哈希表
        // Set<Integer> set = new HashSet<>();
        // for(int i = 0; i < nums.length; i++) set.add(nums[i]);
        // for(int i = 0; i <= nums.length; i++)
        //     if(!set.contains(i)) return i;
        // return -1;

        //解法三 位运算
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i] ^ i;
        }
        return res;

        //解法四 数学
//        int sum = 0;
//        for(int i = 0; i < nums.length; i++){
//            sum += nums[i];
//        }
//        return nums.length * (nums.length + 1) / 2 - sum;
    }

    /**
     * @description: 单词规律
     * 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
     * <p>
     * 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
     * @author: zp
     * @date: 2022/3/1 19:48
     * @param: pattern
     * @param: s
     * @return: boolean
     */
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (words.length != pattern.length()) {
            return false;
        }
        Map<Object, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (!Objects.equals(map.put(pattern.charAt(i), i), map.put(words[i], i))) {
                return false;
            }
        }
        return true;
    }

    /**
     * @description: 给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
     * @author: zp
     * @date: 2022/3/1 20:16
     * @param: nums
     * @return: int
     */
    public int thirdMax(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            Arrays.sort(nums);
            return nums[1];
        }
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            if (!list.contains(num)) {
                list.add(num);
            }
        }
        Collections.sort(list);
        int size = list.size();
        if (list.size() < 3) {
            return list.get(size - 1);
        } else {
            return list.get(size - 3);
        }
    }

    /**
     * @description: 在区间范围内统计奇数数目
     * @author: zp
     * @date: 2022/3/7 19:53
     * @param: low
     * @param: high
     * @return: int
     */
    public int countOdds(int low, int high) {
        if (low % 2 == 1 || high % 2 == 1) {
            return (high - low) / 2 + 1;
        } else {
            return (high - low) / 2;
        }
    }

    /**
     * @description: 去掉最低工资和最高工资后的工资平均值
     * 给你一个整数数组 salary ，数组里每个数都是 唯一 的，其中 salary[i] 是第 i 个员工的工资。
     * <p>
     * 请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。
     * @author: zp
     * @date: 2022/3/7 20:11
     * @param: salary
     * @return: double
     */
    public double average(int[] salary) {
        int max = salary[0];
        int min = salary[0];
        double sum = salary[0];
        for (int i = 1; i < salary.length; i++) {
            sum += salary[i];
            max = Math.max(max, salary[i]);
            min = Math.min(min, salary[i]);
        }
        sum -= max;
        sum -= min;

        return sum / (salary.length - 2);
    }

    /**
     * @description: 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
     * @author: zp
     * @date: 2022/3/7 20:18
     * @param: nums
     * @return: boolean
     */
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
        }
        return false;
    }

    /**
     * @description: 最大子数组和
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * <p>
     * 子数组 是数组中的一个连续部分。
     * @author: zp
     * @date: 2022/3/7 20:24
     * @param: nums
     * @return: int
     */
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    /**
     * @description: 整数的各位积和之差
     * 给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
     * @author: zp
     * @date: 2022/3/8 19:53
     * @param: n
     * @return: int
     */
    public int subtractProductAndSum(int n) {
        int mul = 1;
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            mul *= n % 10;
            n /= 10;
        }
        return mul - sum;
    }

    /**
     * @description: 缺失的第一个正数
     * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
     * <p>
     * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
     * @author: zp
     * @date: 2022/3/8 20:05
     * @param: nums
     * @return: int
     */
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }

    /**
     * @description: 宝石与石头
     * @author: zp
     * @date: 2022/3/8 20:30
     * @param: jewels
     * @param: stones
     * @return: int
     */
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }

        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }

    /**
     * @description: 前K个高频单词
     * @author: zp
     * @date: 2022/3/8 20:32
     * @param: words
     * @param: k
     * @return: java.util.List<java.lang.String>
     */
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.containsKey(word)) {
                map.put(word, map.get(word) + 1);
            } else {
                map.put(word, 1);
            }
        }
        PriorityQueue<Map.Entry<String, Integer>> priorityQueue = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (priorityQueue.size() < k) {
                priorityQueue.offer(entry);
            } else {
                Map.Entry<String, Integer> em = priorityQueue.peek();
                assert em != null;
                if (entry.getValue().compareTo(em.getValue()) == 0 && entry.getKey().compareTo(em.getKey()) < 0) {
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                } else if (em.getValue() < entry.getValue()) {
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                }
            }
        }

        List<String> list = new ArrayList<>();
        while (!priorityQueue.isEmpty()) {
            list.add(priorityQueue.poll().getKey());
            if (list.size() == k) {
                break;
            }
        }
        Collections.reverse(list);
        return list;
    }

    /**
     * @description: 三角形的最大周长
     * 给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。
     * @author: zp
     * @date: 2022/3/9 19:48
     * @param: nums
     * @return: int
     */
    public static int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = length - 1; i > 1; i--) {
            int a = nums[i];
            int b = nums[i - 1];
            int c = nums[i - 2];
            if (a < b + c) {
                return a + b + c;
            }
        }
        return 0;
    }

    /**
     * @description: 找到最近的有相同 X 或 Y 坐标的点
     * 给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i] = [ai, bi] 表示在 (ai, bi) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时，我们称这个点是 有效的 。
     * <p>
     * 请返回距离你当前位置 曼哈顿距离 最近的 有效 点的下标（下标从 0 开始）。如果有多个最近的有效点，请返回下标 最小 的一个。如果没有有效点，请返回 -1 。
     * <p>
     * 两个点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 abs(x1 - x2) + abs(y1 - y2) 。
     * @author: zp
     * @date: 2022/3/9 20:09
     * @param: x
     * @param: y
     * @param: points
     * @return: int
     */
    public int nearestValidPoint(int x, int y, int[][] points) {
        int min = Integer.MAX_VALUE;
        int count = -1;
        for (int i = 0; i < points.length; i++) {
            if (points[i][0] == x || points[i][1] == y) {
                int num = Math.abs(x - points[i][0]) + Math.abs(y - points[i][1]);
                if (num < min) {
                    min = num;
                    count = i;
                }
            }

        }
        return count;
    }

    /**
     * @description: 两个数组的交集 II
     * 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
     * @author: zp （排序加双指针的方式 时间复杂度更低）
     * @date: 2022/3/9 20:22
     * @param: nums1
     * @param: nums2
     * @return: int[]
     */
    public static int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int left = 0;
        int right = 0;
        while (left < nums1.length && right < nums2.length) {
            if (nums1[left] < nums2[right]) {
                left++;
            } else if (nums2[right] < nums1[left]) {
                right++;
            } else if (nums1[left] == nums2[right]) {
                list.add(nums1[left]);
                right++;
                left++;
            }
        }
        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }

    /**
     * @description: 前 K 个高频元素
     * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     * @author: zp
     * @date: 2022/3/9 20:38
     * @param: nums
     * @param: k
     * @return: int[]
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o1.getValue() - o2.getValue();
            }
        });

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (priorityQueue.size() < k) {
                priorityQueue.offer(entry);
            } else {
                Map.Entry<Integer, Integer> em = priorityQueue.peek();
                assert em != null;
                if (entry.getValue() > em.getValue()) {
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                }
            }
        }
        int[] ints = new int[k];
        for (int i = 0; i < k; i++) {
            ints[i] = priorityQueue.poll().getKey();
        }
        return ints;
    }

    /**
     * @description: 键盘行
     * 给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。
     * <p>
     * 美式键盘 中：
     * <p>
     * 第一行由字符 "qwertyuiop" 组成。
     * 第二行由字符 "asdfghjkl" 组成。
     * 第三行由字符 "zxcvbnm" 组成。
     * @author: zp
     * @date: 2022/3/10 20:23
     * @param: words
     * @return: java.lang.String[]
     */
    public static String[] findWords(String[] words) {
        Set<Character> set1 = new HashSet<>();
        Set<Character> set2 = new HashSet<>();
        Set<Character> set3 = new HashSet<>();
        List<String> list = new ArrayList<>();
        char[] str1 = {'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'};
        char[] str2 = {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'};
        char[] str3 = {'z', 'x', 'c', 'v', 'b', 'n', 'm'};
        for (char c : str1) {
            set1.add(c);
        }
        for (char c : str2) {
            set2.add(c);
        }
        for (char c : str3) {
            set3.add(c);
        }
        boolean flag = true;
        String s;
        for (int i = 0; i < words.length; i++) {
            s = words[i].toLowerCase();
            if (set1.contains(s.charAt(0))) {
                for (char c : s.toCharArray()) {
                    if (!set1.contains(c)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    list.add(words[i]);
                }
                flag = true;

            } else if (set2.contains(s.charAt(0))) {
                for (char c : s.toCharArray()) {
                    if (!set2.contains(c)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    list.add(words[i]);
                }
                flag = true;
            } else {
                for (char c : s.toCharArray()) {
                    if (!set3.contains(c)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    list.add(words[i]);
                }
                flag = true;
            }
        }
        String[] ss = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ss[i] = list.get(i);
        }

        return ss;
    }

    /**
     * @description: 数组元素积的符号
     * 已知函数 signFunc(x) 将会根据 x 的正负返回特定值：
     * <p>
     * 如果 x 是正数，返回 1 。
     * 如果 x 是负数，返回 -1 。
     * 如果 x 是等于 0 ，返回 0 。
     * 给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。
     * <p>
     * 返回 signFunc(product) 。
     * @author: zp
     * @date: 2022/3/10 20:51
     * @param: nums
     * @return: int
     */
    public int arraySign(int[] nums) {
        int count = 0;
        for (int num : nums) {
            if (num == 0) {
                return 0;
            }
            if (num < 0) {
                count++;
            }
        }
        if (count % 2 == 0) {
            return 1;
        } else {
            return -1;
        }
    }

    /**
     * @description: 判断能否形成等差数列
     * 给你一个数字数组 arr 。
     * <p>
     * 如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
     * <p>
     * 如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
     * @author: zp
     * @date: 2022/3/10 20:56
     * @param: arr
     * @return: boolean
     */
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        int ave = arr[0] - arr[1];
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] - arr[i + 1] != ave) {
                return false;
            }
        }
        return true;
    }

    /**
     * @description: 快乐数
     * 编写一个算法来判断一个数 n 是不是快乐数。
     * <p>
     * 「快乐数」 定义为：
     * <p>
     * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
     * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
     * 如果这个过程 结果为 1，那么这个数就是快乐数。
     * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
     * @author: zp
     * @date: 2022/3/10 21:00
     * @param: n
     * @return: boolean
     */
    public static boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }

    private static int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    /**
     * @description: 给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换 操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。
     * <p>
     * 如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等，返回 true ；否则，返回 false 。
     * @author: zp
     * @date: 2022/3/10 21:04
     * @param: s1
     * @param: s2
     * @return: boolean
     */
    public boolean areAlmostEqual(String s1, String s2) {
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        Arrays.sort(cs1);
        Arrays.sort(cs2);
        for (int i = 0; i < cs1.length; i++) {
            if (cs1[i] != cs2[i]) {
                return false;
            }
        }
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (!(s1.charAt(i) == s2.charAt(i))) {
                count++;
            }
            if (count > 2) {
                return false;
            }
        }
        return true;
    }

    /**
     * @description: 重塑矩阵
     * @author: zp
     * @date: 2022/3/10 21:48
     * @param: mat
     * @param: r
     * @param: c
     * @return: int[][]
     */
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length;
        int n = mat[0].length;
        if (m * n != r * c) {
            return mat;
        }

        int[][] ans = new int[r][c];
        for (int x = 0; x < m * n; ++x) {
            ans[x / c][x % c] = mat[x / n][x % n];
        }
        return ans;

    }


    private List<Integer> list = new ArrayList<>();

    /**
     * @param root
     * @return List<Integer>
     * @description: N 叉树的前序遍历
     * 给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。
     * <p>
     * n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
     * @author zp
     * @date: 2022/3/12 20:28
     */
    public List<Integer> preorder(Node root) {
        if (root != null) {
            list.add(root.val);
            for (Node node : root.children) {
                preorder(node);
            }
        }
        return list;
    }

    /**
     * @param nums1
     * @param nums2
     * @return int[]
     * @description: 下一个更大元素 I
     * nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
     * <p>
     * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
     * <p>
     * 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
     * <p>
     * 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
     * @author zp
     * @date: 2022/3/12 20:29
     */
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        boolean flag = false;
        for (int i = 0; i < nums2.length; i++) {
            map.put(nums2[i], i);
        }
        for (int i = 0; i < nums1.length; i++) {
            int count = map.get(nums1[i]);
            flag = false;
            if (count < nums2.length - 1) {
                for (int j = count; j < nums2.length; j++) {
                    if (nums2[j] > nums2[count]) {
                        count = nums2[j];
                        flag = true;
                        break;
                    }
                }
                if (flag) {
                    list.add(count);
                } else {
                    list.add(-1);
                }
            } else {
                list.add(-1);
            }
        }
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ints[i] = list.get(i);
        }
        return ints;
    }

    /**
     * @param coordinates
     * @return boolean
     * @description: 缀点成线
     * 给定一个数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。
     * @author zp
     * @date: 2022/3/12 20:56
     */
    public boolean checkStraightLine(int[][] coordinates) {
        int deltaX = coordinates[0][0], deltaY = coordinates[0][1];
        int n = coordinates.length;
        for (int i = 0; i < n; i++) {
            coordinates[i][0] -= deltaX;
            coordinates[i][1] -= deltaY;
        }
        int A = coordinates[1][1], B = -coordinates[1][0];
        for (int i = 2; i < n; i++) {
            int x = coordinates[i][0], y = coordinates[i][1];
            if (A * x + B * y != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * @param arr
     * @return int
     * @description: 所有奇数长度子数组的和
     * 给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
     * <p>
     * 子数组 定义为原数组中的一个连续子序列。
     * <p>
     * 请你返回 arr 中 所有奇数长度子数组的和 。
     * @author zp
     * @date: 2022/3/13 9:51
     */
    public static int sumOddLengthSubarrays(int[] arr) {
        int sum = 0;
        int count = arr.length;
        for (int i = 1; i <= count; i += 2) {
            for (int j = 0; j < count; j++) {
                if (count - j < i) {
                    break;
                }
                for (int k = 0; k < i; k++) {
                    if (j + k >= count) {
                        break;
                    }
                    sum += arr[j + k];
                }
            }
        }
        return sum;
    }

    /**
     * @param nums
     * @description: 移动零
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * <p>
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * @author zp
     * @date: 2022/3/13 11:12
     */
    public static void moveZeroes1(int[] nums) {
        if (nums.length == 1) {
            return;
        }
        int count;
        for (int i = 0; i < nums.length; i++) {
            count = i + 1;
            if (nums[i] == 0) {
                while (count < nums.length) {
                    if (nums[count] != 0) {
                        break;
                    }
                    count++;
                }
                if (count - 1 == nums.length - 1 && nums[count - 1] == 0) {
                    return;
                }
                nums[i] = nums[count];
                nums[count] = 0;
            }
        }

    }

    /**
     * @param accounts
     * @return int
     * @description: 最富有客户的资产总量
     * 给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i​​​​​​​​​​​​ 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。
     * <p>
     * 客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。
     * @author zp
     * @date: 2022/3/13 11:31
     */
    public int maximumWealth(int[][] accounts) {
        int max = 0;
        int sum;
        for (int[] account : accounts) {
            sum = 0;
            for (int j = 0; j < accounts[0].length; j++) {
                sum += account[j];
            }
            max = Math.max(max, sum);
        }
        return max;
    }

    /**
     * @param mat
     * @return int
     * @description: 矩阵对角线元素的和
     * 给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。
     * <p>
     * 请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。
     * @author zp
     * @date: 2022/3/14 19:19
     */
    public static int diagonalSum(int[][] mat) {
        int sum = 0;
        int length = mat.length;
        for (int i = 0; i < length; i++) {
            sum += mat[i][i];
            sum += mat[i][length - 1 - i];
        }
        if (length % 2 != 0) {
            sum -= mat[length / 2][length / 2];
        }
        return sum;
    }

    /**
     * @param word1
     * @param word2
     * @return String
     * @description: 交替合并字符串
     * 给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
     * <p>
     * 返回 合并后的字符串 。
     * @author zp
     * @date: 2022/3/14 19:39
     */
    public static String mergeAlternately(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length(), idx = 0;
        char[] res = new char[len1 + len2];
        for (int i = 0; i < len1 || i < len2; ++i) {
            if (i < len1) {
                res[idx++] = word1.charAt(i);
            }
            if (i < len2) {
                res[idx++] = word2.charAt(i);
            }
        }
        return new String(res);

    }

    /**
     * @param command
     * @return String
     * @description: 设计 Goal 解析器
     * 请你设计一个可以解释字符串 command 的 Goal 解析器 。command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成。Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ，"(al)" 解释为字符串 "al" 。然后，按原顺序将经解释得到的字符串连接成一个字符串。
     * <p>
     * 给你字符串 command ，返回 Goal 解析器 对 command 的解释结果。
     * @author zp
     * @date: 2022/3/14 20:15
     */
    public String interpret(String command) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < command.length(); i++) {
            if (command.charAt(i) == '(') {
                if (command.charAt(i + 1) == ')') {
                    i++;
                    stringBuilder.append('o');
                } else {
                    i++;
                    while (i < command.length() && command.charAt(i) != ')') {
                        stringBuilder.append(command.charAt(i));
                        i++;
                    }
                }
            } else {

                stringBuilder.append(command.charAt(i));
            }
        }
        return stringBuilder.toString();
    }

    /**
     * @param s
     * @param t
     * @return char
     * @description: 找不同
     * 给定两个字符串 s 和 t ，它们只包含小写字母。
     * <p>
     * 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
     * <p>
     * 请找出在 t 中被添加的字母。
     * @author zp
     * @date: 2022/3/14 20:27
     */
    public char findTheDifference(String s, String t) {
        char[] cs = s.toCharArray();
        char[] ts = t.toCharArray();
        Arrays.sort(cs);
        Arrays.sort(ts);
        for (int i = 0; i < s.length(); i++) {
            if (cs[i] != ts[i]) {
                return ts[i];
            }
        }
        return ts[cs.length];
    }

    /**
     * @param ransomNote
     * @param magazine
     * @return boolean
     * @description: 赎金信
     * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
     * <p>
     * 如果可以，返回 true ；否则返回 false 。
     * <p>
     * magazine 中的每个字符只能在 ransomNote 中使用一次。
     * @author zp
     * @date: 2022/3/15 17:44
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < magazine.length(); i++) {
            char c = magazine.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }

        }
        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            if (!map.containsKey(c) || map.get(c) == 0) {
                return false;
            }
            map.put(c, map.get(c) - 1);
        }
        return true;
    }

    /**
     * @param s
     * @return String
     * @description: 转换成小写字母
     * 给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。
     * @author zp
     * @date: 2022/3/15 18:01
     */
    public String toLowerCase(String s) {
        char[] cs = s.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();

        for (char c : cs) {
            if (c >= 65 && c <= 90) {
                stringBuilder.append((char) (c + 32));
            } else {
                stringBuilder.append(c);
            }
        }

        return stringBuilder.toString();
    }

    /**
     * @param s
     * @return String
     * @description: 解码字母到整数映射
     * 给你一个字符串 s，它由数字（'0' - '9'）和 '#' 组成。我们希望按下述规则将 s 映射为一些小写英文字符：
     * <p>
     * 字符（'a' - 'i'）分别用（'1' - '9'）表示。
     * 字符（'j' - 'z'）分别用（'10#' - '26#'）表示。 
     * 返回映射之后形成的新字符串。
     * <p>
     * 题目数据保证映射始终唯一。
     * @author zp
     * @date: 2022/3/15 18:12
     */
    public static String freqAlphabets(String s) {
        Map<String, String> map = new HashMap<>();
        for (int i = 1; i < 27; i++) {
            if (i < 10) {
                map.put(i + "", ((char) (96 + i)) + "");
            } else {
                map.put(i + "#", ((char) (96 + i)) + "");
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        int length = s.length();
        for (int i = length; i > 0; i--) {
            String s1 = s.substring(i - 1, i);
            if ("#".equals(s1)) {
                s1 = s.substring(i - 3, i);
                stringBuilder.append(map.get(s1));
                i -= 2;
            } else {
                stringBuilder.append(map.get(s1));
            }

        }
        return stringBuilder.reverse().toString();
    }

    /**
     * @param list1
     * @param list2
     * @return ListNode
     * @description: 合并两个有序链表
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * @author zp
     * @date: 2022/3/16 17:32
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head;
        if (list1 == null) {
            head = list2;
            return head;
        } else if (list2 == null) {
            head = list1;
            return head;
        } else {
            ListNode temp;
            if (list1.val < list2.val) {
                temp = list1;
                head = temp;
                list1 = list1.next;
            } else {
                temp = list2;
                head = temp;
                list2 = list2.next;
            }
            while (list1 != null || list2 != null) {
                if (list1 == null) {
                    temp.next = list2;
                    list2 = list2.next;
                    temp = temp.next;
                    continue;
                }
                if (list2 == null) {
                    temp.next = list1;
                    list1 = list1.next;
                    temp = temp.next;
                    continue;
                }
                if (list1.val < list2.val) {
                    temp.next = list1;
                    list1 = list1.next;
                } else {
                    temp.next = list2;
                    list2 = list2.next;
                }
                temp = temp.next;

            }
        }
        return head;
    }

    /**
     * @param head
     * @param val
     * @return ListNode
     * @description: 移除链表元素
     * 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
     * @author zp
     * @date: 2022/3/16 18:08
     */
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }

    /**
     * @param root
     * @return int
     * @description: 二叉树的最大深度
     * 给定一个二叉树，找出其最大深度。
     * <p>
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * <p>
     * 说明: 叶子节点是指没有子节点的节点。
     * @author zp
     * @date: 2022/3/16 19:27
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
    }

    /**
     * @param root
     * @return int
     * @description: 左叶子之和
     * 给定二叉树的根节点 root ，返回所有左叶子之和。
     * @author zp
     * @date: 2022/3/16 19:31
     */
    public int sumOfLeftLeaves(TreeNode root) {
        return root != null ? dfs(root) : 0;
    }

    public int dfs(TreeNode node) {
        int ans = 0;
        if (node.left != null) {
            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
        }
        if (node.right != null && !isLeafNode(node.right)) {
            ans += dfs(node.right);
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }

    /**
     * @param words
     * @param order
     * @return boolean
     * @description: 验证外星语词典
     * 某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
     * <p>
     * 给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
     * @author zp
     * @date: 2022/3/17 17:48
     */
    public boolean isAlienSorted(String[] words, String order) {
        int[] index = new int[26];
        for (int i = 0; i < order.length(); ++i) {
            index[order.charAt(i) - 'a'] = i;
        }

        search:
        for (int i = 0; i < words.length - 1; ++i) {
            String word1 = words[i];
            String word2 = words[i + 1];

            for (int k = 0; k < Math.min(word1.length(), word2.length()); ++k) {
                if (word1.charAt(k) != word2.charAt(k)) {
                    if (index[word1.charAt(k) - 'a'] > index[word2.charAt(k) - 'a']) {
                        return false;
                    }
                    continue search;
                }
            }
            if (word1.length() > word2.length()) {
                return false;
            }
        }

        return true;
    }

    /**
     * @param head
     * @return int
     * @description: 二进制链表转整数
     * 给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
     * <p>
     * 请你返回该链表所表示数字的 十进制值 。
     * @author zp
     * @date: 2022/3/17 17:51
     */
    public int getDecimalValue(ListNode head) {
        if (head == null) {
            return 0;
        }
        int ans = 0;
        while (head != null) {
            ans = (ans << 1) + head.val;
            head = head.next;
        }
        return ans;
    }
    //栈的方式
//    public int getDecimalValue(ListNode head) {
//        Stack<Integer> stack = new Stack<>();
//        int sum = 0;
//        int count = 0;
//        while (head!=null){
//            stack.add(head.val);
//            head = head.next;
//        }
//        while (!stack.empty()){
//            if(stack.peek()!=0){
//                sum += Math.pow(2,count);
//            }
//            count++;
//        }
//        return sum;
//    }

    /**
     * @param head
     * @return ListNode
     * @description: 链表的中间结点
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
     * <p>
     * 如果有两个中间结点，则返回第二个中间结点。
     * @author zp
     * @date: 2022/3/17 18:00
     */
    public ListNode middleNode(ListNode head) {
        List<ListNode> listNodes = new ArrayList<>();
        while (head != null) {
            listNodes.add(head);
            head = head.next;
        }
        return listNodes.get(listNodes.size() / 2);
    }

    /**
     * @param head
     * @return ListNode
     * @description: 删除排序链表中的重复元素
     * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
     * @author zp
     * @date: 2022/3/17 18:23
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        head.next = deleteDuplicates(head.next);
        if (head.val == head.next.val) {
            head = head.next;
        }
        return head;
    }

    public boolean isValid(String s) {
        int n = s.length();
        //括号一定是成对出现 如果出现单数 一定不符合要求
        if (n % 2 == 1) {
            return false;
        }
        //把相反的括号对应放入map
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        //创建一个队列
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            //判断输入字符是否在给定字符中
            if (pairs.containsKey(ch)) {
                //判断队列是否有元素 取出来的元素是否对应
                if (stack.isEmpty() || !stack.peek().equals(pairs.get(ch))) {
                    return false;
                }
                //如果有对应的 把元素消费
                stack.pop();
            } else {
                //如果没有对应的括号消费元素 把取出来的字符串放入队列中
                stack.push(ch);
            }
        }
        //最后当循环走完 查看队列中是否还有元素 如果没有就全部完成匹配返回true  如果有就是输入的字符串不符合 返回false
        return stack.isEmpty();
    }

    /**
     * @param arr
     * @return int[]
     * @description: 根据数字二进制下 1 的数目排序
     * 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
     * <p>
     * 如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
     * <p>
     * 请你返回排序后的数组。
     * @author zp
     * @date: 2022/3/18 18:39
     */
    public static int[] sortByBits(int[] arr) {
        int[] bit = new int[10001];
        List<Integer> list = new ArrayList<>();
        for (int x : arr) {
            list.add(x);
            bit[x] = get(x);
        }
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer x, Integer y) {
                if (bit[x] != bit[y]) {
                    return bit[x] - bit[y];
                } else {
                    return x - y;
                }
            }
        });
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public static int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 2;
            x /= 2;
        }
        return res;
    }

    /**
     * @param root
     * @return List<List < Integer>>
     * @description: 二叉树的层序遍历
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     * @author zp
     * @date: 2022/3/18 19:28
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }

        return ret;
    }

    /**
     * @param root
     * @return List<List < Integer>>
     * @description: N叉树的层序遍历
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     * @author zp
     * @date: 2022/3/18 19:28
     */
    public List<List<Integer>> levelOrderN(Node root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                Node node = queue.poll();
                level.add(node.val);
                for (Node node1 : node.children) {
                    queue.offer(node1);
                }
            }
            ret.add(level);
        }

        return ret;
    }

    /**
     * @param root
     * @param val
     * @return TreeNode
     * @description: 二叉搜索树中的搜索
     * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
     * <p>
     * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
     * @author zp
     * @date: 2022/3/19 19:40
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        return searchBST(val < root.val ? root.left : root.right, val);
    }

    /**
     * @param root
     * @return TreeNode
     * @description: 翻转二叉树
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     * @author zp
     * @date: 2022/3/19 19:48
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    /**
     * @param root
     * @param targetSum
     * @return boolean
     * @description: 路径总和
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
     * <p>
     * 叶子节点 是指没有子节点的节点。
     * @author zp
     * @date: 2022/3/19 19:57
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while (!queNode.isEmpty()) {
            TreeNode now = queNode.poll();
            int temp = queVal.poll();
            if (now.left == null && now.right == null) {
                if (temp == targetSum) {
                    return true;
                }
                continue;
            }
            if (now.left != null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if (now.right != null) {
                queNode.offer(now.right);
                queVal.offer(now.right.val + temp);
            }
        }
        return false;
    }

    /**
     * @param nums
     * @return int
     * @description: 数组中重复的数字
     * @author zp
     * @date: 2022/3/19 20:07
     */
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
            set.add(nums[i]);
        }
        return -1;
    }

    /**
     * @param matrix
     * @param target
     * @return boolean
     * @description: 二维数组中的查找
     * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     * @author zp
     * @date: 2022/3/19 20:11
     */
    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) {
            return ans;
        }

        Arrays.sort(nums); // O(nlogn)

        for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
            if (nums[i] > 0) {
                break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 去掉重复情况
            }
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));

                    // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    left++;
                    right--; // 首先无论如何先要进行加减操作
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {  // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return ans;
    }

    /**
     * @param nums
     * @return boolean
     * @description: 单调数列
     * 如果数组是单调递增或单调递减的，那么它是 单调 的。
     * <p>
     * 如果对于所有 i <= j，nums[i] <= nums[j]，那么数组 nums 是单调递增的。 如果对于所有 i <= j，nums[i]> = nums[j]，那么数组 nums 是单调递减的。
     * <p>
     * 当给定的数组 nums 是单调数组时返回 true，否则返回 false。
     * @author zp
     * @date: 2022/3/21 17:23
     */
    public boolean isMonotonic(int[] nums) {
        return isSorted(nums, true) || isSorted(nums, false);
    }

    public boolean isSorted(int[] nums, boolean increasing) {
        int n = nums.length;
        if (increasing) {
            for (int i = 0; i < n - 1; ++i) {
                if (nums[i] > nums[i + 1]) {
                    return false;
                }
            }
        } else {
            for (int i = 0; i < n - 1; ++i) {
                if (nums[i] < nums[i + 1]) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * @param nums
     * @param target
     * @return int[]
     * @description: 在排序数组中查找元素的第一个和最后一个位置
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     * <p>
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * @author zp
     * @date: 2022/3/21 17:47
     */
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    /**
     * @param nums
     * @description: 颜色分类
     * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     * <p>
     * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     * <p>
     * 必须在不使用库的sort函数的情况下解决这个问题。
     * @author zp
     * @date: 2022/3/22 17:13
     */
    public void sortColors(int[] nums) {
        int length = nums.length;
        //加入的标识位 如果在一次排序当中 未进行过任何一次元素交换 说明数组已经有序 可以提前结束循环 节省运行时间
        boolean flag = true;
        for (int j = length; j > 0; j--) {
            for (int i = 0; i < j - 1; i++) {
                if (nums[i] > nums[i + 1]) {
                    flag = false;
                    int swap = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = swap;
                }
            }
            //如果无交换 退出循环结束排序
            if (flag) {
                break;
            } else {
                flag = true;
            }
        }
    }

    /**
     * @param intervals
     * @return int[][]
     * @description: 合并区间
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     * @author zp
     * @date: 2022/3/22 17:39
     */
    public int[][] mergeNums(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    /**
     * @param root
     * @return boolean
     * @description: 平衡二叉树
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * <p>
     * 本题中，一棵高度平衡二叉树定义为：
     * <p>
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     * @author zp
     * @date: 2022/3/22 17:43
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }

    /**
     * @param s
     * @return boolean
     * @description: 重复的子字符串
     * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
     * @author zp
     * @date: 2022/3/22 18:12
     */
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) {
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;

    }

    /**
     * @param digits
     * @return int[]
     * @description: 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
     * <p>
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     * <p>
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     * @author zp
     * @date: 2022/3/24 17:26
     */
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        //跳出for循环，说明数字全部是9
        int[] temp = new int[digits.length + 1];
        temp[0] = 1;
        return temp;
    }

    /**
     * @param num1
     * @param num2
     * @return String
     * @description: 字符串相乘
     * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
     * <p>
     * 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
     * @author zp
     * @date: 2022/3/24 17:30
     */
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        int m = num1.length(), n = num2.length();
        int[] ansArr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        StringBuilder ans = new StringBuilder();
        while (index < m + n) {
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }

    /**
     * @param rowIndex
     * @return List<Integer>
     * @description: 杨辉三角 II
     * 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
     * <p>
     * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
     * @author zp
     * @date: 2022/3/24 17:49
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>(rowIndex + 1);
        long cur = 1;
        for (int i = 0; i <= rowIndex; i++) {
            res.add((int) cur);
            cur = cur * (rowIndex - i) / (i + 1);
        }
        return res;
    }

    /**
     * @param x
     * @param y
     * @return int
     * @description: 汉明距离
     * 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
     * <p>
     * 给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
     * @author zp
     * @date: 2022/3/24 17:57
     */
    public static int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            ret += s & 1;
            s >>= 1;
        }
        return ret;
    }

    /**
     * @param n
     * @return List<String>
     * @description: Fizz Buzz
     * 给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：
     * <p>
     * answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
     * answer[i] == "Fizz" 如果 i 是 3 的倍数。
     * answer[i] == "Buzz" 如果 i 是 5 的倍数。
     * answer[i] == i （以字符串形式）如果上述条件全不满足。
     * @author zp
     * @date: 2022/3/25 17:30
     */
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i >= 5 && i % 3 == 0 && i % 5 == 0) {
                list.add("FizzBuzz");
            } else if (i >= 3 && i % 3 == 0) {
                list.add("Fizz");
            } else if (i >= 5 && i % 5 == 0) {
                list.add("Buzz");
            } else {
                list.add(i + "");
            }
        }
        return list;
    }

    /**
     * @param n
     * @return int
     * @description: 计数质数
     * 给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
     * @author zp
     * @date: 2022/3/25 17:38
     */
    public int countPrimes(int n) {
        int[] a = new int[n + 1];
        int count = 0;
        //先把所有的数变成数组 然后默认都为1
        for (int i = 2; i < n; i++) {
            a[i] = 1;
        }
        //因为 2是第一个质数 所以从2开始 然后把质数倍数的所在位置的数变为0 然后遍历下一个位置为1的数
        for (int i = 2; i < n; i++) {
            if (a[i] == 1) {
                count++;
                for (int j = 2 * i; j < n; j += i) {
                    a[j] = 0;
                }
            }
        }

        return count;
    }

    /**
     * @param n
     * @return boolean
     * @description: 3的幂
     * 给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
     * 整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
     * @author zp
     * @date: 2022/3/25 18:06
     */
    public boolean isPowerOfThree(int n) {
        while (n != 0 && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }

    /**
     * @param n
     * @return int
     * @description: 颠倒二进制位
     * 颠倒给定的 32 位无符号整数的二进制位。
     * <p>
     * 提示：
     * <p>
     * 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
     * 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
     * @author zp
     * @date: 2022/3/26 17:29
     */
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            //res先往左移一位，把最后一个位置空出来，
            //用来存放n的最后一位数字
            res <<= 1;
            //res加上n的最后一位数字
            res |= n & 1;
            //n往右移一位，把最后一位数字去掉
            n >>= 1;
        }
        return res;
    }

    /**
     * @param nums
     * @return TreeNode
     * @description: 将有序数组转换为二叉搜索树
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
     * <p>
     * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
     * @author zp
     * @date: 2022/3/26 17:31
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return f(0, nums.length - 1, nums);
    }

    private TreeNode f(int begin, int end, int[] nums) {
        if (begin > end) {
            return null;
        }
        int mid = (begin + end) / 2; //中间或中间偏左
        return new TreeNode(nums[mid], f(begin, mid - 1, nums), f(mid + 1, end, nums));
    }

    /**
     * @param a
     * @param b
     * @return String
     * @description: 二进制求和
     * 给你两个二进制字符串，返回它们的和（用二进制表示）。
     * <p>
     * 输入为 非空 字符串且只包含数字 1 和 0。
     * @author zp
     * @date: 2022/3/26 17:42
     */
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
    }

    /**
     * @param T
     * @return int[]
     * @description: 每日温度
     * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替
     * <p>
     * 根据题意，从最后一天推到第一天，这样会简单很多。因为最后一天显然不会再有升高的可能，结果直接为0。
     * 再看倒数第二天的温度，如果比倒数第一天低，那么答案显然为1，如果比倒数第一天高，又因为倒数第一天
     * 对应的结果为0，即表示之后不会再升高，所以倒数第二天的结果也应该为0。
     * 自此我们容易观察出规律，要求出第i天对应的结果，只需要知道第i+1天对应的结果就可以：
     * - 若T[i] < T[i+1]，那么res[i]=1；
     * - 若T[i] > T[i+1]
     * - res[i+1]=0，那么res[i]=0;
     * - res[i+1]!=0，那就比较T[i]和T[i+1+res[i+1]]（即将第i天的温度与比第i+1天大的那天的温度进行比较）
     * @author zp
     * @date: 2022/3/28 19:46
     */
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        res[T.length - 1] = 0;
        for (int i = T.length - 2; i >= 0; i--) {
            for (int j = i + 1; j < T.length; j += res[j]) {
                if (T[i] < T[j]) {
                    res[i] = j - i;
                    break;
                } else if (res[j] == 0) {
                    res[i] = 0;
                    break;
                }
            }
        }
        return res;
    }

    /**
     * @param num
     * @param k
     * @return List<Integer>
     * @description: 数组形式的整数加法
     * 整数的 数组形式  num 是按照从左到右的顺序表示其数字的数组。
     * <p>
     * 例如，对于 num = 1321 ，数组形式是 [1,3,2,1] 。
     * 给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。
     * @author zp
     * @date: 2022/3/28 19:51
     */
    public static List<Integer> addToArrayForm(int[] num, int k) {
        int n = num.length;
        LinkedList<Integer> res = new LinkedList<>();
        int sum, carry = 0;
        for (int i = n - 1; i >= 0 || k > 0 || carry != 0; i--) {
            int a = i >= 0 ? num[i] : 0;
            int b = k > 0 ? k % 10 : 0;
            k = k / 10;
            sum = a + b + carry;
            carry = sum / 10;
            res.addFirst(sum % 10);
        }
        return res;
    }

    /**
     * @param s
     * @return int
     * @description: 最后一个单词的长度
     * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
     * <p>
     * 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
     * @author zp
     * @date: 2022/3/28 20:07
     */
    public int lengthOfLastWord(String s) {
        if (s.trim().length() == 0) {
            return 0;
        }
        s = s.trim();
        int count = s.length() - 1;
        int num = 0;
        for (int i = count; i >= 0; i--) {
            if (s.charAt(i) == ' ') {
                break;
            }
            num++;
        }
        return num;
    }

    /**
     * @param matrix
     * @return List<Integer>
     * @description: 螺旋矩阵
     * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     * @author zp
     * @date: 2022/3/29 19:53
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new LinkedList<>();
        }
        int l = 0;
        int r = matrix[0].length - 1;
        int u = 0;
        int d = matrix.length - 1;
        List<Integer> list = new LinkedList<>();
        while (l <= r && u <= d) {
            for (int i = l; i <= r; i++) {
                list.add(matrix[u][i]);
            }
            u++;
            for (int i = u; i <= d; i++) {
                list.add(matrix[i][r]);
            }
            r--;
            for (int i = r; i >= l && u <= d; i--) {
                list.add(matrix[d][i]);
            }
            d--;
            for (int i = d; i >= u && l <= r; i--) {
                list.add(matrix[i][l]);
            }
            l++;
        }
        return list;
    }

    public boolean findRotation(int[][] mat, int[][] target) {
        int n = mat.length, i = 0, j = 0, k = 0;
        for (k = 0; k < 4; k++) {
            for (i = 0; i < n; i++) {
                for (j = 0; j < n; j++) {
                    if (k == 0 && mat[i][j] != target[i][j]) {
                        break;
                    }
                    if (k == 1 && mat[i][j] != target[j][n - i - 1]) {
                        break;
                    }
                    if (k == 2 && mat[i][j] != target[n - i - 1][n - j - 1]) {
                        break;
                    }
                    if (k == 3 && mat[i][j] != target[n - j - 1][i]) {
                        break;
                    }
                }
                if (j != n) {
                    break;
                }
            }
            if (i == n) {
                return true;
            }
        }
        return false;
    }

    /**
     * @param points
     * @param k
     * @return int[][]
     * @description: 最接近原点的 K 个点
     * 给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。
     * <p>
     * 这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。
     * <p>
     * 你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。
     * @author zp
     * @date: 2022/3/30 19:44
     */
    public static int[][] kClosest(int[][] points, int k) {
        int[][] nums = new int[k][2];
        List<List<Integer>> lists = new ArrayList<>();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < points.length; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(points[i][0]);
            list.add(points[i][1]);
            lists.add(list);
            if (i < k) {
                priorityQueue.add((int) (Math.pow(points[i][0], 2) + Math.pow(points[i][1], 2)));
            } else {
                int temp = priorityQueue.peek();
                int num = (int) (Math.pow(points[i][0], 2) + Math.pow(points[i][1], 2));
                if (temp > num) {
                    priorityQueue.poll();
                    priorityQueue.add(num);
                }
            }
        }
        int count = 0;
        while (!priorityQueue.isEmpty()) {
            for (int i = 0; i < lists.size(); i++) {
                if (priorityQueue.isEmpty()) {
                    break;
                }
                int num = priorityQueue.peek();
                if (num == Math.pow(lists.get(i).get(0), 2) + Math.pow(lists.get(i).get(1), 2)) {
                    nums[count][0] = lists.get(i).get(0);
                    nums[count][1] = lists.get(i).get(1);
                    lists.remove(i);
                    priorityQueue.poll();
                    i = 0;
                    count++;
                }
            }
        }

        return nums;
    }

    /**
     * @param nums
     * @param l
     * @param r
     * @return List<Boolean>
     * @description: 等差子数组
     * 给你一个由 n 个整数组成的数组 nums，和两个由 m 个整数组成的数组 l 和 r，后两个数组表示 m 组范围查询，其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。
     * <p>
     * 返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... , nums[r[i]] 可以 重新排列 形成 等差数列 ，answer[i] 的值就是 true；否则answer[i] 的值就是 false 。
     * @author zp
     * @date: 2022/4/1 19:39
     */
    public static List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> list = new ArrayList<>();
        for (int i = 0; i < l.length; i++) {
            list.add(checkNums(nums, l[i], r[i]));
        }
        return list;
    }

    public static boolean checkNums(int[] nums, int l, int r) {
        if (r - l == 1) {
            return true;
        }
        int[] ints = new int[r - l + 1];
        int count = 0;
        for (int i = l; i <= r; i++) {
            ints[count] = nums[i];
            count++;
        }
        Arrays.sort(ints);
        int num = ints[0] - ints[1];
        for (int i = 0; i < ints.length - 1; i++) {
            if (ints[i] - ints[i + 1] != num) {
                return false;
            }
        }
        return true;
    }

    /**
     * @param nums
     * @return int[]
     * @description: 下一个更大元素 II
     * 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
     * <p>
     * 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
     * @author zp
     * @date: 2022/4/1 20:01
     */
    public int[] nextGreaterElements(int[] nums) {
        int length = nums.length;
        int[] ints = Arrays.copyOf(nums, length);
        Arrays.sort(ints);
        int max = ints[length - 1];
        int[] num = new int[length];
        for (int i = 0; i < length; i++) {
            int sum = nums[i];
            if (max == sum) {
                num[i] = -1;
            } else {
                boolean flag = false;
                for (int j = i; j < length; j++) {
                    if (sum < nums[j]) {
                        num[i] = nums[j];
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    for (int j = 0; j < i; j++) {
                        if (sum < nums[j]) {
                            num[i] = nums[j];
                            break;
                        }
                    }
                }
            }
        }
        return num;
    }

    /**
     * @param s
     * @return int
     * @description: 最长回文串
     * 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
     * <p>
     * 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
     * @author zp
     * @date: 2022/4/1 20:19
     */
    public static int longestPalindrome(String s) {
        int[] count = new int[128];
        for (char c : s.toCharArray()) {
            count[c]++;
        }
        int ans = 0;
        for (int v : count) {
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }

    /**
     * @param head
     * @description: 重排链表
     * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     * <p>
     * L0 → L1 → … → Ln - 1 → Ln
     * 请将其重新排列后变为：
     * <p>
     * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
     * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * @author zp
     * @date: 2022/4/3 15:03
     */
    public static void reorderList(ListNode head) {
        LinkedList<ListNode> queue = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            queue.addLast(cur);
            cur = cur.next;
        }
        while (!queue.isEmpty()) {
            if (cur == null) {
                cur = queue.pollFirst();
            } else {
                cur.next = queue.pollFirst();
                cur = cur.next;
            }
            cur.next = queue.pollLast();
            cur = cur.next;
        }
        if (cur != null) {
            cur.next = null;
        }
    }

    /**
     * @param l1
     * @param l2
     * @return ListNode
     * @description: 两数相加 II
     * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
     * <p>
     * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
     * @author zp
     * @date: 2022/4/4 17:14
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        while (l1 != null) {
            s1.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.add(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode head = null;
        while (!s1.isEmpty() || !s2.isEmpty() || carry > 0) {
            int sum = carry;
            sum += s1.isEmpty() ? 0 : s1.pop();
            sum += s2.isEmpty() ? 0 : s2.pop();
            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;
            carry = sum / 10;
        }
        return head;
    }

    /**
     * @param l1
     * @param l2
     * @return ListNode
     * @description: 两数相加
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * <p>
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * <p>
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * @author zp
     * @date: 2022/4/4 17:29
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            int sumVal = l1Val + l2Val + carry;
            carry = sumVal / 10;

            ListNode sumNode = new ListNode(sumVal % 10);
            cursor.next = sumNode;
            cursor = sumNode;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        return root.next;
    }

    /**
     * @param s
     * @param wordDict
     * @return boolean
     * @description: 单词拆分
     * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
     * <p>
     * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
     * @author zp
     * @date: 2022/4/5 18:47
     */
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    /**
     * @param words
     * @return int
     * @description: 唯一摩尔斯密码词
     * @author zp
     * @date: 2022/4/6 20:29
     */
    public int uniqueMorseRepresentations(String[] words) {
        String[] strings = new String[]{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."};
        Map<String, String> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String value = words[i];
            StringBuilder key = new StringBuilder();
            for (int j = 0; j < value.length(); j++) {
                char s = value.charAt(j);
                key.append(strings[s - 97]);
            }
            map.put(key.toString(), value);
        }
        return map.size();
    }

    /**
     * @param s
     * @param goal
     * @return boolean
     * @description: 亲密字符串
     * 给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。
     * <p>
     * 交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。
     * <p>
     * 例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。
     * @author zp
     * @date: 2022/4/6 20:40
     */
    public boolean buddyStrings(String s, String goal) {
        int len1 = s.length(), len2 = goal.length();
        // 1. 字符串长度不相等, 直接返回false
        if (len1 != len2) {
            return false;
        }

        Set<Character> set = new HashSet<>();
        for (int i = 0; i < len1; i++) {
            set.add(s.charAt(i));
        }
        // 2. 字符串相等的时候, 只要有重复的元素就返回true
        if (s.equals(goal)) {
            return set.size() != len1;
        }

        List<Character> list = new ArrayList<>();
        for (int i = 0; i < len1; i++) {
            if (s.charAt(i) != goal.charAt(i)) {
                list.add(s.charAt(i));
                list.add(goal.charAt(i));
            }
            if (list.size() > 4) {
                return false;
            }
        }
        // 3. 字符串有不相等的两个地方, 需要查看它们交换后是否相等即可.
        if (list.size() < 4) {
            return false;
        }
        return list.get(0).equals(list.get(3)) && list.get(1).equals(list.get(2));
    }

    /**
     * @param s1
     * @param s2
     * @return String[]
     * @description: 两句话中的不常见单词
     * 句子 是一串由空格分隔的单词。每个 单词 仅由小写字母组成。
     * <p>
     * 如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却 没有出现 ，那么这个单词就是 不常见的 。
     * <p>
     * 给你两个 句子 s1 和 s2 ，返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。
     * @author zp
     * @date: 2022/4/6 21:01
     */
    public String[] uncommonFromSentences(String s1, String s2) {
        String s = s1 + " " + s2;
        String[] strings = s.split(" ");
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < strings.length; i++) {
            String ss = strings[i];
            if (map.containsKey(ss)) {
                map.put(ss, map.get(ss) + 1);
            } else {
                map.put(ss, 1);
            }
        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                list.add(entry.getKey());
            }
        }
        String[] strs = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            strs[i] = list.get(i);
        }
        return strs;
    }

    /**
     * @param n
     * @return int
     * @description: 统计最大组的数目
     * 给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。
     * <p>
     * 请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。
     * @author zp
     * @date: 2022/4/8 19:49
     */
    public int countLargestGroup(int n) {
        int sum = 0, count = 0, max = 0;
        int[] arrays = new int[37];
        for (int i = 1; i <= n; i++) {
            //遍历数组 当数字是10的整数倍的时候 需要计算数字存放的位置
            if (i % 10 == 0) {
                int num = i;
                sum = 0;
                while (num > 0) {
                    sum += num % 10;
                    num /= 10;
                }
            }
            //使用取模的方式 把数据放到特定的位置上 然后找到存放数据的位置 加一再跟max比较大小 取得最大值
            max = Math.max(arrays[i % 10 + sum] += 1, max);
        }
        //遍历数组 如果等于max数量的元素 就加一 否则不加
        for (int i : arrays) {
            count += i == max ? 1 : 0;
        }
        //最后返回最多元素集合的数量
        return count;
    }

    /**
     * @param s
     * @return String
     * @description: 上升下降字符串
     * 给你一个字符串 s ，请你根据下面的算法重新构造字符串：
     * <p>
     * 从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
     * 从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
     * 重复步骤 2 ，直到你没法从 s 中选择字符。
     * 从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
     * 从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
     * 重复步骤 5 ，直到你没法从 s 中选择字符。
     * 重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
     * 在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
     * <p>
     * 请你返回将 s 中字符重新排序后的 结果字符串 。
     * @author zp
     * @date: 2022/4/8 20:13
     */
    public String sortString(String s) {
        StringBuilder builder = new StringBuilder();
        int[] map = new int[26];
        for (char c : s.toCharArray()) {
            map[c - 'a']++;
        }
        boolean flag;
        do {
            flag = false;
            for (int i = 0; i < 26; i++) {
                if (map[i] > 0) {
                    builder.append((char) (i + 'a'));
                    map[i]--;
                    flag = true;
                }
            }
            for (int i = 25; i >= 0; i--) {
                if (map[i] > 0) {
                    builder.append((char) (i + 'a'));
                    map[i]--;
                    flag = true;
                }
            }
        } while (flag);
        return builder.toString();
    }

    /**
     * @param licensePlate
     * @param words
     * @return String
     * @description: 最短补全词
     * 给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。
     * <p>
     * 补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。
     * <p>
     * 例如：licensePlate = "aBc 12c"，那么它的补全词应当包含字母 'a'、'b' （忽略大写）和两个 'c' 。可能的 补全词 有 "abccdef"、"caaacab" 以及 "cbca" 。
     * <p>
     * 请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。
     * @author zp
     * @date: 2022/4/8 20:32
     */
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] cnt = new int[26];
        for (int i = 0; i < licensePlate.length(); ++i) {
            char ch = licensePlate.charAt(i);
            if (Character.isLetter(ch)) {
                ++cnt[Character.toLowerCase(ch) - 'a'];
            }
        }
        int idx = -1;
        for (int i = 0; i < words.length; ++i) {
            int[] c = new int[26];
            for (int j = 0; j < words[i].length(); ++j) {
                char ch = words[i].charAt(j);
                ++c[ch - 'a'];
            }
            boolean ok = true;
            for (int j = 0; j < 26; ++j) {
                if (c[j] < cnt[j]) {
                    ok = false;
                    break;
                }
            }
            if (ok && (idx < 0 || words[i].length() < words[idx].length())) {
                idx = i;
            }
        }
        return words[idx];
    }

    /**
     * @param paragraph
     * @param banned
     * @return String
     * @description: 给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。
     * <p>
     * 题目保证至少有一个词不在禁用列表中，而且答案唯一。
     * <p>
     * 禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。
     * @author zp
     * @date: 2022/4/9 17:06
     */
    public static String mostCommonWord(String paragraph, String[] banned) {
        paragraph = paragraph.toLowerCase().trim();
        paragraph = paragraph.replace(",", " ").replace(".", " ").replace("!", " ").replace("?", " ").replace(";", " ").replace("'", " ");
        String[] strings = paragraph.split(" ");
        Set<String> set = new HashSet<>(Arrays.asList(banned));
        set.add("");
        Map<String, Integer> map = new HashMap<>();
        int max = 0;
        String str = strings[0];
        for (String s : strings) {
            if (!set.contains(s)) {
                if (map.containsKey(s)) {
                    if (map.get(s) + 1 >= max) {
                        max = map.get(s) + 1;
                        str = s;
                    }
                    map.put(s, map.get(s) + 1);
                } else {
                    map.put(s, 1);
                    if (map.get(s) >= max) {
                        max = map.get(s) + 1;
                        str = s;
                    }
                }
            }
        }
        return str;
    }

    /**
     * @param nums
     * @return List<String>
     * @description: 汇总区间
     * 给定一个  无重复元素 的 有序 整数数组 nums 。
     * <p>
     * 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。
     * 也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
     * <p>
     * 列表中的每个区间范围 [a,b] 应该按如下格式输出：
     * <p>
     * "a->b" ，如果 a != b
     * "a" ，如果 a == b
     * @author zp
     * @date: 2022/4/10 16:43
     */
    public static List<String> summaryRanges(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }
        int start;
        int end;
        List<String> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            start = nums[i];
            end = nums[i];
            while (i + 1 < nums.length && nums[i] + 1 == nums[i + 1]) {
                end = nums[i + 1];
                i++;
            }
            if (start == end) {
                list.add("" + start);
            } else {
                list.add(start + "->" + end);
            }
        }
        return list;
    }

    /**
     * @param n
     * @return boolean
     * @description: Nim 游戏
     * 你和你的朋友，两个人一起玩 Nim 游戏：
     * <p>
     * 桌子上有一堆石头。
     * 你们轮流进行自己的回合， 你作为先手 。
     * 每一回合，轮到的人拿掉 1 - 3 块石头。
     * 拿掉最后一块石头的人就是获胜者。
     * 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
     * @author zp
     * @date: 2022/4/10 17:01
     */
    public boolean canWinNim(int n) {
        return !(n % 4 == 0);
    }

    /**
     * @param nums
     * @return List<Integer>
     * @description: 找到所有数组中消失的数字
     * 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
     * @author zp
     * @date: 2022/4/10 17:19
     */
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++) {
            if (!set.contains(i)) {
                list.add(i);
            }
        }
        return list;
    }

    /**
     * @param arr
     * @return boolean
     * @description: 独一无二的出现次数
     * <p>
     * 给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
     * <p>
     * 如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
     * @author zp
     * @date: 2022/4/12 21:03
     */
    public static boolean uniqueOccurrences(int[] arr) {
        Arrays.sort(arr);
        Set<Integer> set = new HashSet<>();
        int count;
        for (int i = 0; i < arr.length; i++) {
            count = 1;
            while (i + 1 < arr.length && arr[i] == arr[i + 1]) {
                count++;
                i++;
            }
            if (set.contains(count)) {
                return false;
            }
            set.add(count);
        }
        return true;
    }

    /**
     * @param arr
     * @return List<List < Integer>>
     * @description: 给你个整数数组 arr，其中每个元素都 不相同。
     * <p>
     * 请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
     * @author zp
     * @date: 2022/4/12 21:14
     */
    public static List<List<Integer>> minimumAbsDifference(int[] arr) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(arr);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (i + 1 < arr.length) {
                if (Math.abs(arr[i] - arr[i + 1]) < min) {
                    lists.clear();
                    min = Math.abs(arr[i] - arr[i + 1]);
                    lists.add(Arrays.asList(arr[i], arr[i + 1]));
                } else if (Math.abs(arr[i] - arr[i + 1]) == min) {
                    lists.add(Arrays.asList(arr[i], arr[i + 1]));
                }
            }
        }
        return lists;
    }

    /**
     * @param nums
     * @param k
     * @return int
     * @description: 最小差值 I
     * 给你一个整数数组 nums，和一个整数 k 。
     * <p>
     * 在一个操作中，您可以选择 0 <= i < nums 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的整数。对于每个索引 i ，最多 只能 应用 一次 此操作。
     * <p>
     * nums 的 分数 是 nums 中最大和最小元素的差值。 
     * <p>
     * 在对nums中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。
     * @author zp
     * @date: 2022/4/13 21:43
     */
    public static int smallestRangeI(int[] nums, int k) {
        Arrays.sort(nums);
        int max = nums[nums.length - 1];
        int min = nums[0];
        int count = k;
        while (count > 0 && max != min) {
            max--;
            if (max == min) {
                break;
            }
            min++;
            if (max == min) {
                break;
            }
            count--;
        }
        return max - min;
    }

    /**
     * @param nums
     * @return int[]
     * @description: 给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
     * 你可以返回满足此条件的任何数组作为答案。
     * @author zp
     * @date: 2022/4/13 22:05
     */
    public static int[] sortArrayByParity(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        while (right > left) {
            if (nums[left] % 2 == 0) {
                left++;
            } else {
                while (right > left) {
                    if (nums[right] % 2 == 0) {
                        break;
                    }
                    right--;
                }
                if (nums[right] % 2 == 0) {
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                    right--;
                }
            }
        }
        return nums;
    }

    /**
     * @param nums
     * @return int[]
     * @description: 有序数组的平方
     * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     * @author zp
     * @date: 2022/4/14 19:58
     */
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }

    /**
     * @param strs
     * @return int
     * @description: 删列造序
     * 给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。
     * <p>
     * 这些字符串可以每个一行，排成一个网格。例如，strs = ["abc", "bce", "cae"] 可以排列为：
     * <p>
     * abc
     * bce
     * cae
     * 你需要找出并删除 不是按字典序升序排列的 列。在上面的例子（下标从 0 开始）中，列 0（'a', 'b', 'c'）和列 2（'c', 'e', 'e'）都是按升序排列的，而列 1（'b', 'c', 'a'）不是，所以要删除列 1 。
     * <p>
     * 返回你需要删除的列数。
     * @author zp
     * @date: 2022/4/14 20:01
     */
    public static int minDeletionSize(String[] strs) {
        int count = 0;
        char[][] chars = new char[strs.length][strs[0].length()];
        for (int i = 0; i < strs.length; i++) {
            chars[i] = strs[i].toCharArray();
        }
        for (int i = 0; i < chars[0].length; i++) {
            for (int j = 0; j < chars.length - 1; j++) {
                if (chars[j][i] > chars[j + 1][i]) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }

    /**
     * @param s
     * @return int[]
     * @description: 增减字符串匹配
     * 由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
     * <p>
     * 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I' 
     * 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D' 
     * 给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。
     * @author zp
     * @date: 2022/4/14 20:34
     */
    public int[] diStringMatch(String s) {
        int[] nums = new int[s.length() + 1];
        int max = s.length();
        int min = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'I') {
                nums[i] = min;
                min++;
            } else {
                nums[i] = max;
                max--;
            }
        }
        if (s.charAt(s.length() - 1) == 'D') {
            nums[s.length()] = min;
        } else {
            nums[s.length()] = max;
        }
        return nums;
    }

    /**
     * @param candies
     * @param extraCandies
     * @return List<Boolean>
     * @description: 给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
     * <p>
     * 对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。
     * @author zp
     * @date: 2022/4/16 16:17
     */
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int[] nums = Arrays.copyOf(candies, candies.length);
        Arrays.sort(nums);
        int max = nums[nums.length - 1];
        List<Boolean> list = new ArrayList<>();
        for (int candy : candies) {
            list.add(candy + extraCandies >= max);
        }
        return list;
    }

    /**
     * @param arr
     * @return int
     * @description: 找出数组中的幸运数
     * 在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。
     * <p>
     * 给你一个整数数组 arr，请你从中找出并返回一个幸运数。
     * <p>
     * 如果数组中存在多个幸运数，只需返回 最大 的那个。
     * 如果数组中不含幸运数，则返回 -1 。
     * @author zp
     * @date: 2022/4/16 16:23
     */
    public static int findLucky(int[] arr) {
        Arrays.sort(arr);
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int count = 0;
            while (i >= 0 && arr[i] == num) {
                count++;
                i--;
            }
            if (count == num) {
                return num;
            }
            i++;
        }
        return -1;
    }

    /**
     * @param mat
     * @return int[]
     * @description: 对角线遍历
     * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
     * @author zp
     * @date: 2022/4/17 18:06
     */
    public int[] findDiagonalOrder(int[][] mat) {
        int rowLen = mat.length - 1;
        int colLen = mat[0].length - 1;
        List<Integer> list = new ArrayList<>();
        int k = 0, l = 0;
        for (int i = 0; i <= rowLen + colLen; i++) {
            if (i % 2 == 0) {
                for (int j = k; j >= i - 1; j--) {
                    list.add(mat[j][i - j]);
                }
            } else {
                for (int j = l; j >= i - k; j--) {
                    list.add(mat[i - j][j]);
                }
            }
            k = k >= rowLen ? rowLen : k + 1;
            l = l >= colLen ? colLen : l + 1;
        }
        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }

    /**
     * @param nums
     * @return int
     * @description: 最大连续1的个数
     * 给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
     * @author zp
     * @date: 2022/4/17 18:15
     */
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums.length - 1 - i < max) {
                break;
            }
            while (i < nums.length && nums[i] == 1) {
                count++;
                i++;
            }
            max = Math.max(max, count);
            count = 0;
        }
        return max;
    }

    /**
     * @param target
     * @param nums
     * @return int
     * @description: 长度最小的子数组
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * <p>
     * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     * @author zp
     * @date: 2022/4/18 19:59
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int[] ints = Arrays.copyOf(nums, nums.length);
        Arrays.sort(ints);
        if (ints[ints.length - 1] >= target) {
            return 1;
        }
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            int sum = 0;
            int j = i;
            while (j < nums.length && sum < target) {
                sum += nums[j];
                count++;
                j++;
            }
            if (count == nums.length && sum < target) {
                return 0;
            }
            if (sum >= target) {
                min = Math.min(min, count);
            }

        }
        return min;
    }

    /**
     * @param s
     * @return String
     * @description: 反转字符串中的单词 III
     * 给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
     * @author zp
     * @date: 2022/4/18 20:21
     */
    public static String reverseWords3(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        StringBuilder str = new StringBuilder();
        String[] strings = s.split(" ");
        for (String string : strings) {
            str.append(stringBuilder.append(string).reverse());
            str.append(" ");
            stringBuilder.delete(0, string.length());
        }
        return str.toString().trim();
    }

    /**
     * @param nums
     * @return int
     * @description: 寻找旋转排序数组中的最小值
     * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
     * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
     * 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
     * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     * <p>
     * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
     * <p>
     * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
     * @author zp
     * @date: 2022/4/18 20:28
     */
    public int findMin(int[] nums) {
        int temp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < temp) {
                return nums[i];
            }
        }
        return temp;
    }

    /**
     * @param words
     * @return List<String>
     * @description: 数组中的字符串匹配
     * 给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
     * <p>
     * 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
     * @author zp
     * @date: 2022/4/18 20:41
     */
    public static List<String> stringMatching(String[] words) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i != j && words[i].length() <= words[j].length() && words[j].contains(words[i]) && !list.contains(words[i])) {
                    list.add(words[i]);
                }
            }
        }
        return list;
    }

    /**
     * @param head
     * @return ListNode
     * @description: 奇偶链表
     * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
     * <p>
     * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
     * <p>
     * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
     * <p>
     * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
     * @author zp
     * @date: 2022/4/20 19:49
     */
    public ListNode oddEvenList(ListNode head) {
        //如果链表小于3个那么直接返回
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        //定义第一条指针
        ListNode secondhead = head;
        //定义第二条指针
        ListNode oneHead = head.next;
        //定义第一条指针的开始位置
        ListNode one = secondhead;
        //定义第二条指针开始的位置
        ListNode tow = oneHead;
        while (secondhead.next != null && secondhead.next.next != null) {
            //然后这里就是相互的删除中间的元素，也就是逻辑删除
            secondhead.next = secondhead.next.next;
            secondhead = secondhead.next;
            oneHead.next = oneHead.next.next;
            oneHead = oneHead.next;
        }
        secondhead.next = tow;
        return one;
    }

    /**
     * @param head
     * @return int[]
     * @description: 剑指 Offer 06. 从尾到头打印链表
     * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
     * @author zp
     * @date: 2022/4/20 20:00
     */
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.add(head.val);
            head = head.next;
        }
        int[] nums = new int[stack.size()];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = stack.pop();
        }
        return nums;
    }

    public String replaceSpace(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                stringBuilder.append("%20");
            } else {
                stringBuilder.append(s.charAt(i));
            }
        }
        return stringBuilder.toString();
    }

    /**
     * @param s
     * @param n
     * @return String
     * @description: 左旋转字符串
     * 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
     * 请定义一个函数实现字符串左旋转操作的功能。
     * 比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
     * @author zp
     * @date: 2022/4/20 20:17
     */
    public static String reverseLeftWords(String s, int n) {
        int length = s.length();
        if (s.length() < 2) {
            return s;
        }
        n = n % length;
        return s.substring(n) + s.substring(0, n);

    }
}
